package leet142linkedlistcycle

// https://leetcode.cn/problems/linked-list-cycle-ii/
type ListNode struct {
	Val  int
	Next *ListNode
}

// 思路：
// 1. 定义两个指针slow和fast，初始值都为head
// 2. slow指针每次移动一步，fast指针每次移动两步
// 3. 如果slow和fast相遇，说明链表有环
// 4. 如果fast指针到达链表的末尾，说明链表无环
// 5. 如果链表有环，slow和fast相遇后，slow指针不动，fast指针继续向前移动，直到fast指针到达链表的末尾
// 6. 此时slow指针指向的节点就是环的入口节点
// 7. 返回slow指针
// 8. 如果链表无环，返回nil
// 9. 时间复杂度O(n)，空间复杂度O(1)
// 10. 注意：head节点可能为nil，所以要先判断head是否为nil
// 11. 这个题目是一个经典的快慢指针问题，
// 12. 也可以使用哈希表来解决，但是空间复杂度为O(n)，不符合题目要求
// 13. 这里使用快慢指针的方法，
// 14. 先判断链表是否有环，如果有环，再找到环的入口节点
// 15. 这个方法的时间复杂度为O(n)，空间复杂度为O(1)
func DetectCycle(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	slow := head
	fast := head
	// 快慢指针相遇，说明有环
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			break
		}
	}
	if fast == nil || fast.Next == nil {
		return nil
	}
	// 找到环的入口节点
	// 让一个指针从头开始，另一个指针从相遇点开始
	// 两个指针每次都移动一步，直到相遇
	// 相遇的节点就是环的入口节点
	// 此处的原理可以通过数学推导来证明，网上有很多相关的文章
	// 这里就不再赘述了
	slow = head
	for slow != fast {
		slow = slow.Next
		fast = fast.Next
	}
	return slow
}
